Little bit more of the proof.

[yomcat.git] / 432 / assignment 1.tex

\documentclass[11pt,a4paper]{article}

\usepackage{fullpage, amssymb, amsthm, enumerate, amsmath, pictexwd, mathrsfs, ../dcpic}

% yomcat.sty

\newcommand{\mbc}[1]{\textbf{\ensuremath{\mathcal{#1}}}}
\newcommand{\pend}{\hspace*{\fill}{\ensuremath{\square}}}
\newcommand{\es}{\ensuremath{\varnothing}}
\newcommand{\ltr}{\ensuremath{(\Rightarrow)}}
\newcommand{\rtl}{\ensuremath{(\Leftarrow)}}
\newcommand{\mf}[1]{\ensuremath{\mathfrak{#1}}}

% yomcat.sty

\pagestyle{empty}

\setlength{\arraycolsep}{2pt}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}

\begin{document}

\begin{center}
{\bf Victoria University of Wellington}\\[1ex]
{\bf School of Mathematics, Statistics \& Operations Research}\\
\end{center}

\hrule
MATH 432 \hfill
Assignment 1 \hfill
Michael Welsh (301012788)
\vspace{1ex}\hrule\vspace{1ex}

\begin{enumerate}
        \item WOLOG, $G$ is connected. Assume that $G$ doesn't contain a cycle. Then $G$ is a tree. Every tree has at least two leaves (a leaf is a vertex with degree one). But every vertex in $G$ has degree at least two. Therefore $G$ cannot be a tree, and so therefore $G$ contains a cycle. \pend
        \item There are 15 matroids with at most three elements (up to isomorphism):
                \[\begin{tabular}{c|ccc}
                        $M_x$ & $E$ & \mbc{I} & $r(M_x)$ \\ \hline
                        $M_\alpha$ & \es & \es & 0 \\
                        $M_\beta$ & $\{a\}$ & \es & 0 \\
                        $M_\gamma$ & $\{a\}$ & $\{\es, a\}$ & 1 \\
                        $M_\delta$ & $\{a, b\}$ & \es & 0 \\
                        $M_\varepsilon$ & $\{a, b\}$ & $\{\es, a\}$ & 1 \\
                        $M_\zeta$ & $\{a, b\}$ & $\{\es, a, b\}$ & 1 \\
                        $M_\eta$ & $\{a, b\}$ & $\{\es, a, b, \{a, b\}\}$ & 2 \\
                        $M_\vartheta$ & $\{a, b, c\}$ & \es & 0 \\
                        $M_\iota$ & $\{a, b, c\}$ & $\{\es, a\}$ & 1 \\
                        $M_\kappa$ & $\{a, b, c\}$ & $\{\es, a, b\}$ & 1 \\
                        $M_\lambda$ & $\{a, b, c\}$ & $\{\es, a, b, c\}$ & 1 \\
                        $M_\mu$ & $\{a, b, c\}$ & $\{\es, a, b, \{a, b\}\}$ & 2 \\
                        $M_\nu$ & $\{a, b, c\}$ & $\{\es, a, b, c, \{a, b\}, \{a, c\}\}$ & 2 \\
                        $M_\xi$ & $\{a, b, c\}$ & $\{\es, a, b, c, \{a, b\}, \{a, c\}, \{b, c\}\}$ & 2 \\
                        $M_\varpi$ & $\{a, b, c\}$ & $\{\es, a, b, c, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$ & 3
                \end{tabular}\]
                \[\begin{tabular}{c|cc}
                        $M_x$ & Geometric Representation & Associated Graph \\ \hline
                        $M_\alpha$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \enddc & $\bullet$ \\ \\
                        $M_\beta$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(0,0){$a$}
                        \enddc & \begindc{\undigraph}[10]
                        \obj(0,0){}
                        \cmor((0,0)(2,1)(3,0)(2,-1)(0,0)) \pup(3,1){$a$}[2]
                        \enddc \\ \\
                        $M_\gamma$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(2,0){$a$}
                        \enddc & \begindc{\undigraph}[20]
                        \obj(0,0)[A]{}
                        \obj(2,0)[B]{}
                        \mor{A}{B}{$a$}
                        \enddc \\ \\
                        $M_\delta$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(2,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(2,-1)(2,1){}
                        \mor(-1,1)(2,1){}
                        \obj(0,0){$a$}
                        \obj(1,0){$b$}
                        \enddc & \begindc{\undigraph}[10]
                        \obj(0,0){}
                        \cmor((0,0)(2,1)(3,0)(2,-1)(0,0)) \pup(3,1){$b$}[2]
                        \cmor((0,0)(-2,1)(-3,0)(-2,-1)(0,0)) \pup(-3,-1){$a$}[2]
                        \enddc \\ \\
                        $M_\varepsilon$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(0,0){$b$}
                        \obj(2,0){$a$}
                        \enddc & \begindc{\undigraph}[10]
                        \obj(-3,0)[A]{}
                        \obj(0,0)[B]{}
                        \mor{A}{B}{$a$}
                        \cmor((0,0)(2,1)(3,0)(2,-1)(0,0)) \pdown(3,1){$b$}[2]
                        \enddc \\ \\
                        $M_\zeta$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(2,0){$a, b$}
                        \enddc & \begindc{\undigraph}[10]
                        \obj(0,0){}
                        \obj(6,0){}
                        \cmor((0,0)(3,1)(6,0)) \pup(1,1){$a$}[2]
                        \cmor((0,0)(3,-1)(6,0)) \pdown(5,-1){$b$}[2]
                        \enddc \\ \\
                        $M_\eta$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(2,0){$a$}
                        \obj(3,0){$b$}
                        \enddc & \begindc{\undigraph}[25]
                        \obj(-1,0)[A]{}
                        \obj(0,0)[B]{}
                        \obj(1,0)[C]{}
                        \mor{A}{B}{$a$}
                        \mor{B}{C}{$b$}
                        \enddc
                \end{tabular}\]
                \[\begin{tabular}{c|cc}
                        $M_x$ & Geometric Representation & Associated Graph \\ \hline
                        $M_\vartheta$ & \begindc{\undigraph}[13]
                        \mor(-2,-1)(2,-1){}
                        \mor(-2,-1)(-2,1){}
                        \mor(2,-1)(2,1){}
                        \mor(-2,1)(2,1){}
                        \obj(-1,0){$a$}
                        \obj(0,0){$b$}
                        \obj(1,0){$c$}
                        \enddc & \begindc{\undigraph}[10]
                        \obj(0,0){}
                        \cmor((0,0)(2,1)(3,0)(2,-1)(0,0)) \pdown(3,1){$b$}[2]
                        \cmor((0,0)(-2,1)(-3,0)(-2,-1)(0,0)) \pdown(-3,1){$a$}[2]
                        \cmor((0,0)(-1,-2)(0,-3)(1,-2)(0,0)) \pdown(-1,-3){$c$}[2]
                        \enddc \\ \\
                        $M_\iota$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(2,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(2,-1)(2,1){}
                        \mor(-1,1)(2,1){}
                        \obj(0,0){$b$}
                        \obj(1,0){$c$}
                        \obj(3,0){$a$}
                        \enddc & \begindc{\undigraph}[10]
                        \obj(0,0)[A]{}
                        \obj(4,0)[B]{}
                        \mor{A}{B}{$a$}
                        \cmor((0,0)(-2,1)(-3,0)(-2,-1)(0,0)) \pdown(-3,1){$b$}[2]
                        \cmor((4,0)(6,1)(7,0)(6,-1)(4,0)) \pdown(7,1){$c$}[2]
                        \enddc \\ \\
                        $M_\kappa$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(0,0){$c$}
                        \obj(2,0){$a, b$}
                        \enddc & \begindc{\undigraph}[10]
                        \obj(0,0){}
                        \obj(6,0){}
                        \cmor((0,0)(3,1)(6,0)) \pup(1,1){$a$}[2]
                        \cmor((0,0)(3,-1)(6,0)) \pup(5,-1){$b$}[2]
                        \cmor((6,0)(8,1)(9,0)(8,-1)(6,0)) \pup(9,1){$c$}[2]
                        \enddc \\ \\
                        $M_\lambda$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(2,0){$a, b, c$}
                        \enddc & \begindc{\undigraph}[10]
                        \obj(0,0)[A]{}
                        \obj(6,0)[B]{}
                        \mor{A}{B}{$b$}
                        \cmor((0,0)(3,2)(6,0)) \pup(1,2){$a$}[2]
                        \cmor((0,0)(3,-2)(6,0)) \pup(5,-2){$c$}[2]
                        \enddc \\ \\
                        $M_\mu$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(0,0){$c$}
                        \obj(2,0){$a$}
                        \obj(3,0){$b$}
                        \enddc & \begindc{\undigraph}[10]
                        \obj(0,0)[a]{}
                        \obj(4,0)[b]{}
                        \obj(8,0)[c]{}
                        \mor{a}{b}{$a$}
                        \mor{b}{c}{$b$}
                        \cmor((0,0)(-2,1)(-3,0)(-2,-1)(0,0)) \pdown(-3,1){$c$}[2]
                        \enddc \\ \\
                        $M_\nu$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(2,0){$a$}
                        \obj(3,0){$b, c$}
                        \enddc & \begindc{\undigraph}[9]
                        \obj(0,0)[a]{}
                        \obj(6,0)[b]{}
                        \obj(12,0){}
                        \mor{a}{b}{$a$}
                        \cmor((6,0)(9,1)(12,0)) \pdown(7,1){$b$}[2]
                        \cmor((6,0)(9,-1)(12,0)) \pdown(11,-1){$c$}[2]
                        \enddc \\ \\
                        $M_\xi$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(2,0)[a]{$a$}
                        \obj(3,0){$b$}
                        \obj(4,0)[c]{$c$}
                        \mor{a}{c}{}
                        \enddc & \begindc{\undigraph}[10]
                        \obj(-2,-1)[a]{} % bottom left
                        \obj(2,-1)[b]{} % bottom right
                        \obj(0,2)[c]{} % top
                        \mor{a}{c}{$a$}[1,2]
                        \mor{b}{c}{$b$}[-1,2]
                        \mor{a}{b}{$c$}[-1,2]
                        \enddc \\ \\
                        $M_\varpi$ & \begindc{\undigraph}[13]
                        \mor(-1,-1)(1,-1){}
                        \mor(-1,-1)(-1,1){}
                        \mor(1,-1)(1,1){}
                        \mor(-1,1)(1,1){}
                        \obj(2,0){$a$}
                        \obj(3,0){$b$}
                        \obj(4,0){$c$}
                        \enddc &\begindc{\undigraph}[12]
                        \obj(-2,-1)[a]{} % bottom left
                        \obj(2,-1)[b]{} % bottom right
                        \obj(0,2)[c]{} % top
                        \obj(0,0)[d]{} % middle
                        \mor{d}{c}{$a$}[1,2]
                        \mor{d}{a}{$b$}[1,2]
                        \mor{d}{b}{$c$}[1,2]
                        \enddc
                \end{tabular}\]
        \item \begin{enumerate}[(i)]
                \item \[\begin{vmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{vmatrix} = 1\]
                So a basis for the matroid is
                \[\begin{Bmatrix} \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 0 \\ 1 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 1 \\ 0 \\ 1 \end{bmatrix} \end{Bmatrix}\]
                \item A spanning circuit for the matroid is
                \[\begin{Bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}, & \begin{bmatrix} 1 \\ 0 \\ 1 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 1 \\ 0 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \end{bmatrix} \end{Bmatrix}\]
                \item A triangle of the matroid is
                \[\begin{Bmatrix} \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \end{bmatrix} \end{Bmatrix}\]
                \item A five element hyperplane for the matroid is
                \[\begin{Bmatrix} \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix}, & \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 1 \\ 0 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \end{bmatrix} \end{Bmatrix}\]
                So a triad of the matroid is the complement of that set, which is
                \[\begin{Bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}, & \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}, & \begin{bmatrix} 1 \\ 0 \\ 1 \\ 1 \end{bmatrix} \end{Bmatrix}\]
                \item An independent hyperplane of the matroid is
                \[\begin{Bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}, & \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}, & \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, & \begin{bmatrix} 1 \\ 0 \\ 1 \\ 1 \end{bmatrix} \end{Bmatrix}\]
        \end{enumerate}
        \item \[\begindc{\undigraph}[4]
                \obj(10,10)[b]{$b$} % bottom left
                \obj(37,14)[g]{$g$} % middle
                \obj(50,10)[c]{$c$} % bottom right
                \obj(30,40)[a]{$a$} % top
                \obj(30,10)[f]{$f$} % bottom centre
                \obj(20,25)[d]{$d$} % right middle
                \obj(40,25)[e]{$e$} % left middle
                \mor{b}{c}{}
                \mor{a}{b}{}
                \mor{a}{c}{}
                \cmor((20,25)(23,14)(30,10)(37,14)(40,25)) \pup(11,13){}[2]
        \enddc\]
        \item Up to isomorphism, the simple rank three matroids with six elements are:
        \[\begindc{\undigraph}[12] %\varrho
                \obj(0,0)[a]{$a$}
                \obj(3,0)[b]{$b$}
                \obj(6,0)[c]{$c$}
                \obj(0,3)[d]{$d$}
                \obj(3,3)[e]{$e$}
                \obj(6,3)[f]{$f$}
                \mor{a}{c}{}
                \mor{d}{f}{}
        \enddc\]
        \\
        \[\begindc{\undigraph}[2] %\sigma
                \obj(10,10)[b]{$b$} % bottom left
                \obj(50,10)[c]{$c$} % bottom right
                \obj(30,40)[a]{$a$} % top
                \obj(30,10)[f]{$e$} % bottom centre
                \obj(20,25)[d]{$f$} % right middle
                \obj(40,25)[e]{$d$} % left middle
                \mor{b}{c}{}
                \mor{a}{b}{}
                \mor{a}{c}{}
        \enddc\]
        \\
        \[\begindc{\undigraph}[2] %\tau
                \obj(10,10)[b]{$b$} % bottom left
                \obj(50,10)[c]{$c$} % bottom right
                \obj(30,40)[a]{$a$} % top
                \obj(30,10)[f]{$e$} % bottom centre
                \obj(20,25)[d]{$f$} % right middle
                \obj(40,25)[e]{$d$} % left middle
                \mor{a}{b}{}
                \mor{a}{c}{}
        \enddc\]
        \\
        \[\begindc{\undigraph}[2] %\upsilon
                \obj(10,10)[b]{$b$} % bottom left
                \obj(50,10)[c]{$c$} % bottom right
                \obj(30,40)[a]{$a$} % top
                \obj(30,20)[e]{$e$} % bottom centre
                \obj(20,25)[f]{$f$} % right middle
                \obj(40,25)[d]{$d$} % left middle
                \mor{f}{c}{}
                \mor{a}{b}{}
                \mor{a}{c}{}
                \mor{b}{d}{}
        \enddc\]
        \\
        \[\begindc{\undigraph}[12] %\psi
                \obj(0,0)[a]{$a$}
                \obj(3,0)[b]{$b$}
                \obj(6,0)[c]{$c$}
                \obj(9,0)[d]{$d$}
                \obj(3,3)[e]{$e$}
                \obj(6,3)[f]{$f$}
                \mor{a}{d}{}
        \enddc\]
        \\
        \[\begindc{\undigraph}[12] %\omega
                \obj(0,0)[a]{$a$}
                \obj(3,0)[b]{$b$}
                \obj(6,0)[c]{$c$}
                \obj(9,0)[d]{$d$}
                \obj(12,0)[e]{$e$}
                \obj(6,3)[f]{$f$}
                \mor{a}{e}{}
        \enddc\]
        \\
        \[\begindc{\undigraph}[12] %\phi
                \obj(0,0)[a]{$a$}
                \obj(3,0)[b]{$b$}
                \obj(6,0)[c]{$c$}
                \obj(0,3)[d]{$d$}
                \obj(3,3)[e]{$e$}
                \obj(6,3)[f]{$f$}
                \mor{a}{c}{}
        \enddc\]
        \\
        \[\begindc{\undigraph}[12] %\chi
                \obj(0,0)[a]{$a$}
                \obj(3,0)[b]{$b$}
                \obj(6,0)[c]{$c$}
                \obj(0,3)[d]{$d$}
                \obj(3,3)[e]{$e$}
                \obj(6,3)[f]{$f$}
        \enddc\]
        \item To start with, I'm going to assume that {\bf I2} is supposed to read:
        If $I_1 \in \mbc{I}$, and $I_2 \subseteq I_1$, then $I_2 \in \mbc{I}$. \\
        The first two axioms are identical to the independence axioms, so all that remains to show that the extension axiom ({\bf I3a}) holds. \\
        Suppose that $I_1$ and $I_2$ are members of \mbc{I} such that $|I_1| < |I_2|$, but {\bf I3a} fails for this pair. So, $\forall e \in I_2 - I_1$, $I_1 \cup e \notin \mbc{I}$. Let $I_1 \cup I_2 = X \subseteq E$. This means that $I_1$ is a maximal member of \mbc{I} contained in $X$. Now extend $I_2$ to $I'_2$, which is maximal in $X$. So $|I_2'| > |I_2| > |I_1|$, contradicting {\bf I3}. \\
        Hence {\bf I3a} must hold, and so $(E, \mbc{I})$ is a matroid. \pend
        \item \begin{enumerate}
                \item[\ltr] Assume that $V$ is linearly independent. Construct the matrix corresponding to $V$. Then $|V| = |V^T| \neq 0$. Apply the row operation $r_k \to r_k + \alpha r_j$ to $V^T$, forming the matrix $(V')^T$. As the only row operation used is adding a multiple of a row to another row, $|V^T| = |(V')^T| = |V'| \neq 0$, and hence $V'$ is linearly independent.
                \item[\rtl] Assume that $V'$ is linearly independent. Construct the matrix corresponding to $V'$. Then $|V'| = |(V')^T| \neq 0$. Apply the row operation $r_k \to r_k - \alpha r_j$ to $(V')^T$, forming the matrix $V^T$. As the only row operation used is adding a multiple of a row to another row, $|(V')^T| = |V^T| = |V| \neq 0$, and hence $V$ is linearly independent. \pend
        \end{enumerate}
        \item Suppose that $U_{2,4}$ is graphic. Then there exists a connected graph $G$ such that $M(G) = U_{2,4}$. Let $n$ be the number of vertices in $G$. Therefore a spanning tree of $G$ contains $n - 1$ edges, and so the rank of $M(G)$ is $n - 1$. \\
        But $U_{2,4}$ has 4 elements, so $n = 4$. By the above reasoning, $r(U_{2,4}) = 4 - 1 = 3$. But $r(U_{2,4}) = 2$, which is a contradiction. Therefore $U_{2,4}$ is not graphic. \pend
        \item \begin{enumerate}[(i)]
                \item Let $E = \{ \alpha, \beta, \gamma \}$. Then let $\mbc{I}_1 = \{ \es, \{\gamma\} \}$ and $\mbc{I}_2 = \{ \es, \{\alpha\}, \{\beta\}, \{\alpha, \beta\}\}$. So $\mbc{I}_1 \cup \mbc{I}_2 = \{ \es, \{\alpha\}, \{\beta\}, \{\gamma\}, \{\alpha, \beta\}\}$. Then $(E, \mbc{I}_1 \cup \mbc{I}_2)$ is not a matroid, as setting $I_1 = \{\alpha, \beta\}$ and $I_2 = \{\gamma\}$ breaks {\bf I3}.
                \item Let $\mf{J} = \{I_1 \cup I_2 | I_1 \in \mbc{I}_1,\ I_2 \in \mbc{I}_2\}$. \begin{enumerate}
                        \item[{\bf I1}:] $\es \in \mbc{I}_1$, $\es \in \mbc{I}_2$. So $\es \cup \es = \es \in \mf{J}$.
                        \item[{\bf I2}:] Let $J_1 \in \mf{J}$, and $J_2 \subset J_1$. Then $J_1 = I_1 \cup I_2$, so $J_2 \subset I_1 \cup I_2$. If $J_2 \subseteq I_1$, then $J_2 = I_{1'} \cup \es$, where $I_{1'} \subseteq I_1$, so $I_{1'} \in \mbc{I}_1$. Therefore $J_2 \in \mf{J}$. Likewise if $J_2 \subseteq I_2$. \\
                        The other case is when $J_2 = I_{1'} \cup I_{2'}$, where $I_{1'} \subseteq I_1$ and $I_{2'} \subseteq I_2$, so $I_{1'} \in \mbc{I}_1$ and $I_{2'} \in \mbc{I}_2$. Hence $J_2 \in \mf{J}$.
                        \item[{\bf I3}:] Let $J_1$ and $J_2$ be elements of \mf{J} such that $|J_2| < |J_1|$. Let $J_1 = I_1 \cup I_2$ and let $J_2 = I'_1 \cup I'_2$. As $|J_2| < |J_1|$, either $|I'_1| < |I_1|$ or $|I'_2| < |I_2|$. \\
                        WOLOG, $|I'_1| < |I_1|$. Then there exists $e \in I_1 - I'_1$ such that $I'_1 \cup e \in \mbc{I}_1$. So $(I_1' \cup e) \cup I'_2 = (I'_1 \cup I'_2) \cup e \in \mf{J}$.
                \end{enumerate}
                As these three conditions hold, $(E, \mf{J})$ is a matroid. \pend
                \item  Let $E = \{ \alpha, \beta, \gamma \}$. Then let $\mbc{I}_1 = \{ \es, \{\alpha\}, \{\beta\}, \{\gamma\}, \{\alpha, \beta\}, \{\beta, \gamma\} \}$ and $\mbc{I}_2 = \{ \es, \{\alpha\}, \{\beta\}, \{\gamma\}, \{\alpha, \beta\}, \{\alpha, \gamma\}\}$. So $\mbc{I}_1 \cap \mbc{I}_2 = \{ \es, \{\alpha\}, \{\beta\}, \{\gamma\}, \{\alpha, \beta\}\}$. Then $(E, \mbc{I}_1 \cap \mbc{I}_2)$ is not a matroid, as setting $I_1 = \{\alpha, \beta\}$ and $I_2 = \{\gamma\}$ breaks {\bf I3}.
        \end{enumerate}
        \item Let $\mf{B} = \mbc{B} \cup \{X\}$. \begin{enumerate}
                \item[{\bf B1}:] \mf{B} is obviously non-empty, as both \mbc{B} and $\{X\}$ have something in them.
                \item[{\bf B2}:] Let $B_1$ and $B_2$ be two distinct elements of \mf{B}, and let $x \in B_1 - B_2$. Let $y \in B_2 - B_1$ and consider $(B_1 - x) \cup y$. There are 4 cases, depending on where $B_1$ and $B_2$ come from. \begin{enumerate}[(1)]
                        \item $B_1 \subseteq \mbc{B}$, $B_2 \subseteq \mbc{B}$. \\
                        As \mbc{B} is the set of bases of $M$, $B_1$ and $B_2$ are bases of $M$, and so $(B_1 - x) \cup y \subseteq \mf{B}$.
                        \item $B_1 \subseteq \{X\} - \mbc{B}$, $B_2 \subseteq \mbc{B}$. \\
                        As $B_1$ is a subset of $X$, and $X$ is a hyperplane, $B_1 - x$ is independent. $B_2$ is a basis of $M$, and is therefore independent. $|B_2| > |B_1 - x|$, so there exists $y \in B_2 - (B_1 - x)$ such that $(B_1 - x) \cup y$ is independent. Furthermore, $|(B_1 - x) \cup y| = |B_2|$, and so $(B_1 - x) \cup y$ is also a basis, and hence $(B_1 - x) \cup y \in \mf{B}$.
                        \item $B_1 \subseteq \mbc{B}$, $B_2 \subseteq \{X\} - \mbc{B}$. \\
                        This is the same as Case 2. Just swap $B_1$ and $B_2$, and $x$ and $y$ as required.
                        \item $B_1 \subseteq \{X\}-\mbc{B}$, $B_2 \subseteq \{X\}-\mbc{B}$. \\
                        $B_1$ is a subset of $\{X\}$, and so is $B_2$. Then $B_1 - B_2 \subseteq \{X\}$ and $B_2 - B_1 \subseteq \{X\}$. Pick $x \in B_1 - B_2 \subseteq \{X\}$, so $x \in \{X\}$ and hence $B_1 - x \subseteq \{X\}$. Now pick $y \in B_2 - B_1 \subseteq \{X\}$. Therefore $y \in \{X\}$ and hence $(B_1 - x) \cup y \subseteq \{X\} \subseteq \mf{B}$.
                        \end{enumerate}
                        As these two conditions hold, \mf{B} is the set of bases of a matroid on the ground set $E$. \pend
        \end{enumerate}
        \item Let $C_1$ and $C_2$ be a pair of distinct circuits and let $e \in C_1 \cap C_2$. By Lemma 2.3, there is a circuit, $C_3$, contained in $(C_1 \cup C_2) - e$. If this circuit contains an element of $C_1 - C_2$ (or an element of $C_2 - C_1$), then we win. \\
        So, $C_3 \cap (C_1 - C_2) = \es = C_3 \cap (C_2 - C_1)$. Therefore $C_3 \subseteq C_1 \cap C_2$. So $C_3 \subseteq C_1$ and $C_3 \subseteq C_2$. By Proposition 2.2, $C_3 = C_1$ and $C_3 = C_2$. However, $C_1$ and $C_2$ are distinct, so this cannot happen. Hence $C_3$ contains an element $f$, that is (WOLOG), in $C_1 - C_2$. \pend
\end{enumerate}

\end{document}